This invention relates to communications, and more particularly to cryptographic communications systems and methods.
With the development of computer technology, the transfer of information in digital form has rapidly increased. There are many applications, including electronic mail systems, bank systems and data processing systems, where the transferred information must pass over communications channels which may be monitored by electronic eavesdroppers. While the degree of security required may vary for various applications, it is generally important for all of these examples that the substance of particular communications pass directly from a sender to an intended receiver without intermediate parties being able to interpret the transferred message. In addition, there are further instances where information in computer memory banks must be protected from snoopers who have access to the memory through data processing networks.
In addition to these privacy requirements, authentication of the source of a message must often be insured along with the verification and security of the message content. For example, in banking applications, it is required that a signed document, such as a bank draft, be authenticated as being actually signed by the indicated signator. Furthermore, in many applications, it is desirable to further require safeguards against signature forgery by a message recipient.
In the prior art, a number of cryptographic encoding and decoding techniques are readily available to provide some degree of privacy and authentication for digital communications, for example, the data encryption standards adopted by the National Bureau of Standards, see Federal Register, Mar. 17, 1975, Volume 40, No. 52 and Aug. 1, 1975, Volume 40, No. 149.
In general, cryptographic systems are adapted to transfer a message between remote locations. Such systems include at least one encoding device at a first location and at least one decoding device at a second location, with the encoding and decoding devices all being coupled to a communication channel. For digital systems, the message is defined to be a digital message, M, that is, a sequence of symbols from some alphabet. In practice, the alphabet is generally chosen to be the binary alphabet consisting of the symbols 0 and 1.
Each encoding device is an apparatus which accepts two inputs: a message-to-be-encoded, M, and an encoding key or operator, E. Each encoding device transforms the message M in accordance with the encryption operator to produce an encoded version C of the message (which is denoted as the ciphertext) where C=E(M). The encoding key and the ciphertext are also digital sequences.
Each decoding device is an apparatus which accepts two inputs: a ciphertext-to-be-decoded C and a decoding key or operator, D. Each decoding device transforms the ciphertext in accordance with the decryption operator to produce a decoded version M' of the ciphertext where M'=D(C), or M'=D(E(M)). Like the encoding key, the decoding key and decoded message M' are also digital sequences. The encoding and decoding keys are selected so that M'=M for all messages M.
In operation, a message, once encoded into ciphertext, is transmitted over the channel to a recipient who decodes the received ciphertext to obtain the original message M. Thus, a recipient sees the original message M as the output of his decoding device.
To a large degree, the quality of performance of a cryptographic system depends on the complexity of the encoding and decoding devices. Regarding the problem of ensuring privacy of communications for a system where an eavesdropper can listen to every message transmitted on the communications channel (which might, for example, be a radio link), the effectiveness of the system depends upon the ability to ensure that the eavesdropper is unable to understand any such overheard messages. In the prior art systems, the sender and recipient arrange to have corresponding encoding and decoding keys which are kept secret from the eavesdropper, so that even if the eavesdropper knows the construction of the encoding and decoding devices, he would not be able to decode the messages he hears, even after hearing a large number of messages. In practice, however, this constraint results in extremely complex and correspodingly expensive equipment. A disadvantage of the prior art systems results from the general requirement that the pre-arranged encoding and decoding keys must be delivered in a secure fashion (often by courier) to the sender and receiver, respectively, to enable communication through the systems.
The "public-key cryptosystem" described by Diffie and Hellman, "New Directions In Cryptography", IEEE Transactions on Information Theory (Nov. 1976), in principle, provides enciphered communication between arbitrary pairs of people, without the necessity of their agreeing on an enciphering key beforehand. The Diffie and Hellman system also provides a way of creating for a digitized document a recognizable, unforgeable, document-dependent, digitized signature whose authenticity the signer cannot later deny.
In a public-key cryptosystem, each user (e.g. user A) places in a public file an enciphering operator, or key, E.sub.A. User A keeps to himself the details of the corresponding deciphering key D.sub.A which satisfies the equation EQU D.sub.A (E.sub.A (M))=M,
for any message M. In order for the public key system to be practical, both E.sub.A and D.sub.A must be efficiently computable. Furthermore, user A must not compromise D.sub.A when revealing E.sub.A. That is, it should not be computationally feasible for an eavesdropper to find an efficient way of computing D.sub.A, given only a specification of the enciphering key E.sub.A (even though a very inefficient way exists: to compute D.sub.A (C), just enumerate all possible messages M until one such that E.sub.A (M)=C is found. Then D.sub.A (C)=M.). In a public key system, a judicious selection of keys ensures that only user A is able to compute D.sub.A efficiently.
Whenever another user (e.g. user B) wishes to send a message M to A, he looks up E.sub.A in the public file and then sends the enciphered message E.sub.A (M) to user A. User A deciphers the message by computing D.sub.A (E.sub.A (M))=M. Since D.sub.A is not derivable from E.sub.A in a practical way, only user A can decipher the message E.sub.A (M) sent to him. If user A wants to send a response to user B, user A enciphers the message using user B's encryption key E.sub.B, also available in the public file. Therefore no transactions between users A and B, such as exchange of secret keys, are required to initiate private communication. The only "setup" required is that each user who wishes to receive private communication must place his enciphering key E in the public file.
The public key approach of Diffie and Hellman is also useful in principle to provide signed digital messages that are both message-dependent and signer-dependent. The recipient of a "signed" message not only knows the message substance, but also can provide that the message originated from the identified sender. A signed message precludes the possibility that a recipient could modify the received message by changing a few characters or that the recipient could attach the received signature to any message whatsoever. This is a particular problem for digital messages inasmuch as electronic "cutting and pasting" of sequences of characters are generally undetectable in the final product.
In order to implement signatures on messages transferred between two users, e.g. user A and user B, in accordance with the Diffie and Hellman system, each user has encoding keys E.sub.A and E.sub.B, respectively, on a public file and decoding keys D.sub.A and D.sub.B, respectively, privately held. Each user's encoding and decoding keys must effect permutations of the same message space S, so that the following relation s hold: EQU D.sub.A (E.sub.A (M))=M EQU E.sub.A (D.sub.A (M))=M EQU D.sub.B (E.sub.B (M))=M EQU E.sub.B (D.sub.B (M))=M
for any message M.
When user A wants to send user B a "signed" document M, user A first uses his own decryption key D.sub.A to transform M into a signed message word M.sub.s =D.sub.A (M). User A then uses user B's encryption key E.sub.B (from the public file) to generate a signed ciphertext word C.sub.s =E.sub.B (M.sub.s)=E.sub.B (D.sub.A (M)), which is sent to user B. User B initially uses his secret decryption key D.sub.B to reduce the signed ciphertext C.sub.s to a signed message word in accordance with D.sub.B (C.sub.s)=D.sub.B (E.sub.B (M.sub.s))=M.sub.s. Now using user A's encoding key E.sub.A (available from the public file), user B decodes the signed message word in accordance with E.sub.A (M.sub.s)=E.sub.A)=M.
User A cannot deny having sent user B this message, since no one but A could have created M.sub.s =D.sub.A (M), provided that D.sub.A is not computable from E.sub.A. Furthermore, user B can show that the public key E.sub.A is necessary to extract the message M so that user B has "proof" that user A has signed the document. User B cannot modify M to a different version M', since then user B would have to create the corresponding signature D.sub.A (M') as well. Therefore user B must have received a document "signed" by A, which he can "prove" that A sent, but which B cannot modify in any detail.
While the public-key cryptosystem principles as described above, and their potential use as a means of implementing digital "signatures", are known in the prior art, there are no practical implementations which are known, either with or without signature.
Accordingly, it is an object of this invention to provide a system and method for implementing a private communications system.
It is another object to provide a system and method for establishing a private communications system for transmission of signed messages.
It is still another object to provide a system and method for implementing a public key cryptographic communications system.
It is a further object to provide a system and method for encoding and decoding digital data.